package com.example.Arithmetic.Arithmetic;

import java.util.Arrays;

/**
 * 日期：2023/12/30
 * 时间：15:03
 * 描述：不相交集合实现（并查集和）
 * union和find方法，查找和赋值，所以叫不相交集合
 */
public class DisjointSet {
    int i[];
    int[] size;
    //    初始化数据，索引代表元素，值代表和谁联通
    public DisjointSet(int size) {
        this.i=new int[size];
        this.size=new int[size];
        for (int j = 0; j < size; j++) {
            i[j] = j;
        }
    }

    //    寻找谁是老大
    public int find(int x) {
        if (i[x] == x) {
            return x;
        }
//        压缩路径
        return i[x] = find(i[x]);
    }

    // union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
    public void union(int x, int y) {
        if (size[x] < size[y]) {
            int t = x;
            x = y;
            y = t;
        }
        i[y] = x;
        size[x] = size[x] + size[y];
    }

    @Override
    public String toString() {
        return "内容："+Arrays.toString(i) + "\n大小：" + Arrays.toString(size);
    }

    public static void main(String[] args) {
        DisjointSet set=new DisjointSet(5);

        set.union(1, 2);
        set.union(3, 4);
        set.union(1, 3);
        System.out.println(set);
    }
}
